1. Field of the Invention
This invention relates to a very efficient process for clipping polygons against a window in computer graphic systems and displays. A modification of the invention clips polylines against a window very efficiently.
2. Description of Prior Art
On a computer graphics output device, such as a video display terminal, a plotter, etc., an area (the window) is always defined either explicitly as a portion or the whole of the display area of the device, or implicitly in which case the whole display area is used, as the area to display a picture. This area may or may not be big enough or oriented such that to contain the whole picture. The actions to be taken to handle the portions of the picture that fall outside the display area, when the window is the whole display area of the output device, are not standardized among output devices. If the window is a sub-area of the display area, the display of the portions of the picture that fall outside the window will intrude possibly other windows and defeat the purpose of specifying a window. The portions of the picture that fall outside the window should be first eliminated before the picture is displayed in the window. This process of eliminating portions of a picture that fall outside the window is called clipping. The process of eliminating portions of a polygon that fall outside a window is called polygon clipping. The process of eliminating portions of a polyline that fall outside a window is called polyline clipping.
The representation of the window, polygons, and other names and labels useful in describing the polygon clipping process are now discussed generally.
The window is defined as the set of points (x, y) such that EQU x.sub.left .ltoreq.x.ltoreq.x.sub.right EQU y.sub.bottom .ltoreq.y.ltoreq.y.sub.top
where x=x.sub.left, x=x.sub.right, y=y.sub.bottom and y=y.sub.top are the boundary lines of the window (See FIG. 1 (a)). The first two boundary lines are called the vertical boundary lines and the last two are called the horizontal boundary lines. The boundary lines also partition the two dimensional plane into nine regions. The regions delimited by all four boundary lines is the window. The regions delimited by three boundary lines are the edge regions. The regions delimited by two boundary lines are the corner regions. The nine regions are depicted in FIG. 1 (a).
The points (x.sub.left, y.sub.bottom), (x.sub.left, y.sub.top), (x.sub.right, y.sub.bottom) and (x.sub.right, y.sub.top) are called the window corners of the left bottom, left top, right bottom and right top corner regions respectively.
Each boundary line also partitions the two-dimensional plane into two half-planes. One half-plane contains the window and is called the visible side of the boundary line. The other half-plane is called the invisible side of the boundary line (See FIG. 1 (b)). A vertex, an edge, or a group of vertices is outside a boundary line if it is on the invisible side of the boundary line. It is inside a boundary line if it is on the visible side of the boundary line.
A point is said to be visible if it is inside the window. Otherwise, it is invisible.
The input polygon is represented by a sequence of the vertices of the polygon .upsilon..sub.0, .upsilon..sub.1, . . . , .upsilon..sub.n-1 . Each vertex is represented by an ordered pair (x.sub.i, y.sub.i), 0.ltoreq.i.ltoreq.n-1 with x.sub.n-1 =x.sub.0 and y.sub.n-1 =y.sub.0. Appending the first vertex to the end of the vertex list will always satisfy this requirement. Each two consecutive vertices represent an edge of the polygon. The edges combine to form the boundary of the polygon. The vertices delimiting an edge are called the endpoints of the edge. An edge is said to be visible if both endpoints of the edge are in the window. An edge is said to be invisible if the whole edge is outside the window. Otherwise, the edge is partly visible or non-invisible.
Suppose the first endpoint (x.sub.1, y.sub.1) is outside two boundary lines. The first endpoint of the clipped edge, if the line segment is partly visible, can be on either of the boundary lines. Suppose the two boundary lines are the top and the left boundary lines. The following inequality is true if the first endpoint of the clipped edge is on the left boundary line. ##EQU1## where (x.sub.2,y.sub.2) is the second endpoint, .delta.x=x.sub.2 -x.sub.1 and .delta.y=y.sub.2 -y.sub.1. The equation can be transformed to ##EQU2## if .delta.y and .delta.x are non-zero. The two quotients are called the quotients of the top and the left boundary lines with respect to the edge, respectively. Quotients are used to compute intersection point.
Given a polygon .upsilon..sub.0, .upsilon..sub.1, . . . , .upsilon..sub.n-1 and a point P=(x,y) that is not on the boundary of the polygon or the window, sum the angles .angle..upsilon..sub.0 P.upsilon..sub.1,.angle..upsilon..sub.1 P.upsilon..sub.2, . . . , .angle..upsilon..sub.n-2 P.upsilon..sub.n-1 in radians. Dividing the sum by 2 .pi. yields a whole number, the wrap number of the point P. The counterclockwise direction is the positive direction, just like in mathematics. A point on the boundary of the window or the polygon has no wrap number.
The result of clipping the polygon .upsilon..sub.0, .upsilon..sub.1, . . . , .upsilon..sub.n-1 against a window is another polygon either empty when the whole polygon is outside the window, or .upsilon.'.sub.0, .upsilon.'.sub.1, . . . , .upsilon.'.sub.m-1 such that .upsilon.'.sub.i, 0.ltoreq.i.ltoreq.m-1 is either a visible vertex of the original polygon, an intersection point of an edge of the original polygon and the window boundary, or a window corner. The resultant polygon must satisfy the following criteria:
(1) All points in the window but not on the window boundary that have wrap numbers with respect to the original polygon should also have wrap numbers with respect to the resultant polygon. The wrap numbers of these points with respect to the resultant polygon should be identical to the wrap numbers they have with respect to the original polygon. This criterion prevents the modification of the topology of the part of the polygon that is in the window so that the filling process that might be used after the polygon clipping process can be done correctly. PA0 (2) Given a sublist of vertices l= .upsilon..sub.i,.upsilon..sub.i+1, . . . ,.upsilon..sub.j in the polygon such that .upsilon..sub.i and .upsilon..sub.j are invisible but .upsilon..sub.i+l, .upsilon..sub.i+2, . . . , .upsilon..sub.j-1 are visible, the result of clipping this sublist must be .GAMMA..sub.1, .upsilon..sub.i+1, .upsilon..sub.i+2, . . . , .upsilon..sub.j-1, .GAMMA..sub.2 , where .GAMMA..sub.1 and .GAMMA..sub.2 are the intersection points the edges .upsilon..sub.i .upsilon..sub.i+1 and .upsilon..sub.j-1 .upsilon..sub.j make with the window boundary respectively. PA0 (3) Suppose l'= .upsilon..sub.i, .GAMMA..sub.1, .omega..sub.1, .omega..sub.2, . . . , .omega..sub.k, .GAMMA..sub.2, .upsilon..sub.j , a sub-list of vertices of the resultant polygon after clipping l= .upsilon..sub.i,.upsilon..sub.i+1, . . . ,.upsilon..sub.j , where .upsilon..sub.i+1, .upsilon..sub.i+2, . . . , .upsilon..sub.j-1 are invisible vertices, none of the edges .upsilon..sub.i+1 .upsilon..sub.i+2, .upsilon..sub.i+2 .upsilon..sub.i+3, . . . , .upsilon..sub.j2 .upsilon..sub.j-1 intersects the window boundary, .GAMMA..sub.1 is the intersection point of the edge .upsilon..sub.i .upsilon..sub.i+1 and the window boundary, .GAMMA..sub.2 is the intersection point of the edge .upsilon..sub.j-1 .upsilon..sub.j and the window boundary, and .omega..sub.j, for all j such that 1.ltoreq.j.ltoreq.k are window corners included to connect .GAMMA..sub.1 and .GAMMA..sub.2. PA0 (4) If a polygon is entirely outside the window, the resultant polygon should be empty . This criterion prevents the display of extraneous edges when the resultant polygon is empty. PA0 (1) Both endpoints are inside the boundary line. The second endpoint is sent to the output. PA0 (2) Both endpoints are outside the boundary line. Both are discarded. PA0 (3) The first endpoint is inside the boundary line and the second endpoint is outside the boundary line. Compute the intersection point the edge makes with the boundary line and output it. PA0 (4) The first endpoint is outside the boundary line and the second endpoint is inside the boundary line. Compute the intersection point the edge makes with the boundary line, output it, and then output the second endpoint. PA0 (1) The extended edge originates from a corner region; intersects a boundary line to enter an edge region; intersects another boundary line to enter the window; intersects a boundary line to exit to an edge region; and finally intersects the last boundary line to enter a corner region. If the edge overlaps the first portion of the extended edge, then output the corner of the corner region it originates from. If the edge overlaps the portion of the extended edge that enters the window, then compute the intersection point and output it. If the first endpoint of the edge is inside the window, output it. If the second endpoint of the edge is inside the window, output it as well. If the edge overlaps the portion of the extended edge that exits the window, compute the intersection point on the window boundary and output the intersection point. PA0 (2) The extended edge originates from a corner region; intersects a boundary line to enter an edge region; intersects another boundary line to enter another corner region on the same invisible side as the originating corner region; intersects a boundary line to enter an edge region; and finally intersects a boundary line to enter another corner region. If the edge overlaps the first portion of the extended edge, then output the corner of the originating corner region. If the edge overlaps the portion of the extended edge that exits the second corner region, then the corner of that corner region is also sent to the output.
Take any three consecutive vertices .mu..sub.1, .mu..sub.2, and .mu..sub.3 from l'. The edges .mu..sub.1 .mu..sub.2, and .mu..sub.2 .mu..sub.3 must not intersect each other except at .mu..sub.2. This criterion restricts the number of window corners included to connect two intersection points.
The intersection points .GAMMA..sub.1 and .GAMMA..sub.2 are called two consecutive intersection points.
There are two well-known polygon clipping algorithms, the Sutherland-Hodgman and the Liang-Barsky algorithms (See Ivan E. Sutherland and Gary W. Hodgroan, Reentrant polygon clipping, Communications of the ACM, volume 17 (1974), no. 1, page 32-42 and You-Dong Liang and Brian A. Barsky, An analysis and algorithm for polygon clipping, Communications of the ACM, volume 26 (1983), no. 11, page 868-877). They will be discussed briefly in this section.
The Sutherland-Hodgman Algorithm. The Sutherland-Hodgman algorithm clips the polygon through a pipeline with a different boundary line in each stage of the pipeline. Suppose the boundary lines are ordered in this manner: the left, right, bottom and then the top boundary lines. The algorithm first clips the polygon against the left boundary .line. The result of this stage is then fed to be clipped against the fight boundary line in the second stage. Similarly, the results of the second, and the third stages are fed to be clipped against the bottom and top boundary lines respectively. The resultant polygon of the fourth stage is the resultant polygon of the clipping process.
In each stage, each of the edges of the input polygon is handled separately into four cases.
In this algorithm, a vertex in each stage is processed twice. The first time the vertex is processed as the second endpoint of an edge. The second time it is processed as the first endpoint of the next edge. An edge is processed twice in every stage before it is discarded. A further inefficiency is that some computation of intersection points are ultimately wasted as the intersection points computed are not part of the resultant polygon. This occurs when an intersection point computed in a stage proves to be outside the boundary line in a later stage. The operations used for the computation of the intersection points are all wasted. Furthermore, the last two criteria for resultant polygons are not met by this algorithm. The criterion that a polygon that is outside the window should result in an empty resultant polygon is not met can be shown by a simple example. Refer to FIG. 5 now. In FIG. 5(a), the original polygon is a, b, c, d, e, f, g, h, i, j, k, l, a and the window is labeled as such. Without loss of generality, suppose the arrangement of the boundary lines in the pipeline is the left, the bottom, the right, and the top. FIG. 5(b) shows the resultant polygon of stage one of clipping the original polygon against the left boundary line, m, n, o, p, q, r, s, t, u, v, w, x, m . This polygon is then fed to the stage to be clipped against the bottom boundary line. The resultant polygon of this second stage is shown in FIG. 5(c), y, z, A, B, C, D, E, F, G, H, I, J, y , which is then fed to be clipped against the right boundary line. The resultant polygon of this third stage is shown in FIG. 5(d) and it is K, L, M, N, O, P, Q, R, S, T, U, V, K . This resultant polygon of the third stage is then fed to the fourth stage to be clipped against the top boundary line. The resultant polygon of this fourth stage and therefore the resultant polygon of the whole polygon clipping process is shown in FIG. 5(e), W, X, Y, Z, .alpha., .beta., .gamma., .delta., W . The resultant polygon of the polygon clipping process is therefore not empty. This example also provides an instance that the third criterion for resultant polygon is not met by the Sutherland-Hodgman algorithm. Also, the coordinates of the vertices, n, w, v, o, H, A, G, O, R, N, S, W, Z, .alpha., and .delta. are unnecessary computed because ultimately nothing should be displayed.
The Liang-Barsky Algorithm. The Liang-Barsky algorithm also handles each edge separately. Each edge is parameterized and clipped against the window. When processing an edge, the edge is extended to infinity at both ends. There are two cases.
In this algorithm, a vertex is also processed twice. Each edge must also be parameterized. This is a significant source of inefficiency because the parameterization requires arithmetic operations that are not required by the Sutherland-Hodgman algorithm and the present invention. Again, the last two criteria for the inclusion of vertices in the resultant polygons are not met by this algorithm. Referring to FIG. 6, the Liang-Barsky algorithm includes the window corner A although the whole polygon is clearly outside the window.